﻿using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using WordNet.Core;
using WordNet.Core.Graph;

namespace GraphTest
{
    [TestClass]
    public class SAPTest
    {
        [TestMethod]
        public void CanFindAncestorTest()
        {
            int[][] dag = new int[][] { new[] { 7, 3 }, new[] { 8, 3 }, new[] { 3, 1 }, new[] { 4, 1 }, new[] { 5, 1 }, new[] { 9, 5 }, new[] { 10, 5 }, new[] { 11, 10 }, new[] { 6, 10 }, new[] { 1, 0 }, new[] { 2, 0 } };
            Digraph g = new Digraph(dag.Length);
            for (int i = 0; i < dag.Length; i++)
            {
                g.AddEdge(dag[i][0], dag[i][1]);
            }
            ASPath shortesPathToAncestor = new ASPath(g);
            Assert.AreEqual(4, shortesPathToAncestor.Length(3, 11));
            Assert.AreEqual(1, shortesPathToAncestor.Ancestor(3, 11));

            Assert.AreEqual(3, shortesPathToAncestor.Length(9, 6));
            Assert.AreEqual(5, shortesPathToAncestor.Ancestor(9, 6));

            Assert.AreEqual(4, shortesPathToAncestor.Length(7, 2));
            Assert.AreEqual(0, shortesPathToAncestor.Ancestor(7, 2));

            Assert.AreEqual(3, shortesPathToAncestor.Length(4, 9));
            Assert.AreEqual(1, shortesPathToAncestor.Ancestor(4, 9));
        }

        [TestMethod]
        public void CanFindAncestorOverlapTest()
        {
            int[][] dag = new int[][] { new[] { 1, 0 }, new[] { 1, 2 }, new[] { 2, 3 }, new[] { 3, 4 }, new[] { 4, 5 }, new[] { 5, 0 } };
            Digraph g = new Digraph(dag.Length);
            for (int i = 0; i < dag.Length; i++)
            {
                g.AddEdge(dag[i][0], dag[i][1]);
            }

            ASPath shortesPathToAncestor = new ASPath(g);
            Assert.AreEqual(2, shortesPathToAncestor.Length(1, 5));
            Assert.AreEqual(0, shortesPathToAncestor.Ancestor(1, 5));

            Assert.AreEqual(3, shortesPathToAncestor.Length(1, 4));
            Assert.AreEqual(4, shortesPathToAncestor.Ancestor(1, 4));
            
            Assert.AreEqual(3, shortesPathToAncestor.Length(0, 3));
            Assert.AreEqual(0, shortesPathToAncestor.Ancestor(0, 3));
        }

        [TestMethod]
        public void CanFindAncestorCircleTest()
        {
            int[][] dag = new int[][] { new[] { 7, 6 }, new[] { 6,3 }, new[] { 3, 0 }, new[] { 0, 6 }, new[] { 3, 2 }, new[] { 3,4 },new[] {4,1}, new[] {1,3}, new[]{5,4}, new[]{5,8} };
            Digraph g = new Digraph(dag.Length);
            for (int i = 0; i < dag.Length; i++)
            {
                g.AddEdge(dag[i][0], dag[i][1]);
            }
            
            ASPath shortesPathToAncestor = new ASPath(g);
            Assert.AreEqual(2, shortesPathToAncestor.Length(5, 3));
            Assert.AreEqual(4, shortesPathToAncestor.Ancestor(5, 3));

            Assert.AreEqual(4, shortesPathToAncestor.Length(5, 7));
            Assert.AreEqual(4, shortesPathToAncestor.Ancestor(5, 7));

            Assert.AreEqual(2, shortesPathToAncestor.Length(0, 1));
            Assert.AreEqual(0, shortesPathToAncestor.Ancestor(0, 1));

            Assert.AreEqual(4, shortesPathToAncestor.Length(0, 5));
            Assert.AreEqual(4, shortesPathToAncestor.Ancestor(0, 5));
        }

        [TestMethod]
        public void CanFindAncestorOnDirectedPath()
        {
            var dag = DigraphTest.dgNoCycle;
            Digraph g = new Digraph(dag.Length);
            for (int i = 0; i < dag.Length; i++)
            {
                g.AddEdge(dag[i][0], dag[i][1]);
            }

            ASPath shortesPathToAncestor = new ASPath(g);
            Assert.AreEqual(2, shortesPathToAncestor.Length(0, 7));
            Assert.AreEqual(6, shortesPathToAncestor.Ancestor(0, 7));

            Assert.AreEqual(4, shortesPathToAncestor.Length(8, 10));
            Assert.AreEqual(10, shortesPathToAncestor.Ancestor(8,10));

            Assert.AreEqual(3, shortesPathToAncestor.Length(3, 6));
            Assert.AreEqual(4, shortesPathToAncestor.Ancestor(3, 6));
            
            Assert.AreEqual(2, shortesPathToAncestor.Length(2, 6));
            Assert.AreEqual(6, shortesPathToAncestor.Ancestor(2, 6));
        }
        
        [TestMethod]
        public void CanFindAncestorOnDirectedCycles()
        {
            var cycles = DigraphTest.dgCycle;
            Digraph g = new Digraph(cycles.Length);
            for (int i = 0; i < cycles.Length; i++)
            {
                g.AddEdge(cycles[i][0], cycles[i][1]);
            }
            ASPath shortesPathToAncestor = new ASPath(g);
           
            // ambiguous ancestor
            Assert.AreEqual(2, shortesPathToAncestor.Length(6, 8));
            Assert.AreEqual(9, shortesPathToAncestor.Ancestor(6, 8));

            Assert.AreEqual(2, shortesPathToAncestor.Length(8, 6));
            Assert.AreEqual(6, shortesPathToAncestor.Ancestor(8, 6));
        }
    }
}